package leetcode.中等;

import leetcode.entity.ListNode;
import leetcode.utils.ListNodeUtils;
import org.junit.Test;
import org.w3c.dom.NodeList;

import java.util.*;

public class leetcode19_删除链表倒数第n个节点 {

    @Test
    public void test(){

        ListNode listNode = ListNodeUtils.createListNode(5);
        ListNode listNode1 = delListNodes(listNode, 2);
        System.out.println(listNode1);
    }


    /**
     * 遍历全表获得长度，创建节点0
     *
     */
    public ListNode delListNodes(ListNode node,int n){
        ListNode first = new ListNode(0,node);
        int length = getLength(node);
        ListNode cur = first;
        for(int i = 0;i<length-n;i++){
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return  first.next;
    }


    public int getLength(ListNode node){
        int i = 1;
        while(node.next!=null){
            i++;
            node = node.next;
        }
        return i;
    }


    /**
     * 新建栈，第删除第n个出栈的
     */
    public ListNode delListNodeByStack(ListNode node,int n){
        ListNode first = new ListNode(0,node);
        Deque<ListNode> stack = new LinkedList<>();
        ListNode cur = first;

        while(cur!=null){
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0;i<n;++i){
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return first.next;
    }
}
